﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using text.dfs;
using text.huishuo;
using text.Images;
using text.LinkedList;
using text.StrProblem;

namespace text
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public class Solution
    {

        public int Rob(TreeNode root)
        {
            int[] dp=dfs(root);
            return Math.Max(dp[0],dp[1]);
        }
        public int[] dfs(TreeNode node)
        {
            int[] dp = new int[2];
            if (node == null) return dp;
            int[] left=dfs(node.left);
            int[] right = dfs(node.right);
            //0 代表该节点不抢
            dp[0] = Math.Max(left[0],left[1])+Math.Max(right[0],right[1]);
            //1 代表该节点抢
            dp[1] = node.val + left[0] + right[0];
            return dp;
           
        }
    }
    public class ListNode {
          public int val;
          public ListNode next;
          public ListNode(int x) { val = x; }
      }
    class Program
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="prices">本金</param>
        /// <param name="rate">年利息</param>
        /// <param name="month">期数时间</param>
        /// <returns></returns>
        public static double findAverage(double prices, double rate, int month)
        {
            double mRate = (rate / 12) + 1.0;//月利率
            return prices * Math.Pow(mRate, month) / findPow(month - 1, mRate);
        }
        public static double findPow(int index, double x)
        {
            if (index == 0)
            {
                return 1;
            }
            return Math.Pow(x, index) + findPow(--index, x);
        }
        public static void  dic(int n, int curIndex)
        {
            if (n == curIndex)
            {
                return;
            }
            dic(n, curIndex+1);
            for (int i = 0; i <= curIndex; i++)
            {
                Console.Write('*');
            }
            Console.WriteLine();
        }
        public static Decimal di(int n, int curIndex, Decimal cur)
        {
            if (n == curIndex)
            {
                return cur;
            }
            cur = Convert.ToDecimal( 1 / Math.Pow(2, curIndex))+cur;
            return di(n, curIndex + 1, cur) ;
        }
        static void Main(string[] args)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            
        }
        /// <summary>
        /// 对比两个字符串相同的最大长度
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns></returns>
        public static int FindLength(int[] A, int[] B)//DP方法
        {
            int m = A.Length;
            int n = B.Length;
            int[,] bq = new int[10, 10];
            int res = 0;
            for (int i = 0; i < m; i++)//初始化bq长度
            {
                for (int j = 0; j < n; j++)
                {
                    bq[i, j] = 0;
                }
            }
            for (int i = 1; i <= m; i++)//初始化bq长度
            {
                for (int j = 1; j <= n; j++)
                {
                    if (A[i - 1] == B[j - 1])
                    {
                        bq[i, j] = bq[(i - 1), (j - 1)] + 1;
                    }
                    res = Math.Max(bq[i, j], res);
                }
            }
            return res;
        }
        /// <summary>
        /// 滑动窗口
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns></returns>
        public static int OtherFindLength(int[] A, int[] B)//DP方法
        {
            int m = A.Length;
            int n = B.Length;
            int res = 0;
            for (int i = 0; i < n; i++)//滑动b窗口
            {
                int len = Math.Min(m, n - i);
                int maxlen = getMaxLen(A, B, 0, i, len);
                res = Math.Max(res, maxlen);
            }
            for (int i = 0; i < m; i++)
            {
                int len = Math.Min(n, m - i);
                int maxlen = getMaxLen(A, B, i, 0, len);
                res = Math.Max(res, maxlen);
            }
            return res;
        }
        public static int getMaxLen(int[] A, int[] B,int curA,int curB,int len)//DP方法
        {
            int m = A.Length;
            int n = B.Length;
            int maxlen = 0;
            int res = 0;
            for (int i = 0; i < len; i++)
            {
                
                if (curB + i < n && curA +i < m && A[curA+i] == B[curB+i])
                    res++;
                else {
                    res = 0;
                }
                maxlen = Math.Max(maxlen, res);
            }
            return maxlen;
        }
    }
}
